﻿#define _CRT_SECURE_NO_WARNINGS 1;
#include <iostream>
using namespace::std;

//class Person {
//
//public:
//	virtual void BuyTicket(int val = 1) { cout << "买票-全价格"<<val << endl; }
//};
//
//class Student : public Person {
//public:
//	virtual void BuyTicket(int val = 0) { cout << "买票-半价票" <<val<< endl; }
//};
//
//void Func(Person& people)
//{
//	people.BuyTicket();
//}
//
//int main()
//{
//	Person a;
//	Student b;
//
//	Func(a);
//	Func(b);
//
//	return 0;
//}

//class A 
//{
//public:
//	virtual void func(int val = 1) { std::cout << "A->" << val << std::endl; }
//	virtual void test() { func(); }
//};
//class B : public A
//{
//public:
//	void func(int val = 0) override { std::cout << "B->" << val << std::endl; }
//};
//int main(int argc, char* argv[])
//{
//	B* p = new B;
//	p->test();
//	p->func();
//	return 0;
//}


//class Base
//{
//public:
//	virtual void Func1()
//	{
//		cout << "Func1()" << endl;
//	}
//protected:
//	int _b = 1;
//	char _ch = 'x';
//};
//int main()
//{
//	Base b;
//	cout << sizeof(b) << endl;
//}

//class Base {
//public:
//	virtual void func1() { cout << "Base::func1" << endl; }
//	virtual void func2() { cout << "Base::func2" << endl; }
//	void func5() { cout << "Base::func5" << endl; }
//protected:
//	int a = 1;
//};
//class Derive : public Base
//{
//public:
//	// 重写基类的func1
//	virtual void func1() { cout << "Derive::func1" << endl; }
//	virtual void func3() { cout << "Derive::func1" << endl; }
//	void func4() { cout << "Derive::func4" << endl; }
//protected:
//	int b = 2;
//};
//int main()
//{
//	int i = 0;
//	static int j = 1;
//	int* p1 = new int;
//	const char* p2 = "xxxxxxxx";
//	printf("栈:%p\n", &i);
//	printf("静态区:%p\n", &j);
//	printf("堆:%p\n", p1);
//	printf("常量区:%p\n", p2);
//	Base b;
//	Derive d;
//	Base* p3 = &b;
//	Derive* p4 = &d;
//	printf("Person虚表地址:%p\n", *(int*)p3);
//	printf("Student虚表地址:%p\n", *(int*)p4);
//	printf("虚函数地址:%p\n", &Base::func1);
//	printf("普通函数地址:%p\n", &Base::func5);
//	return 0;
//}
//#include "BinarySearchTree.h"

//int main()
//{
//	int a[] = { 8,3,1,10,1,6,4,7,14,13 };
//	BSTree<int> t1;
//	for (const auto& e : a)
//	{
//		t1.Insert(e);
//	}
//
//	t1.InOrder();
//	t1.Erase(8);
//	t1.InOrder();
//	return 0;
//}


template<class K, class V>
struct BSTNode
{
	// pair<K, V> _kv;
	K _key;
	V _value;
	BSTNode<K, V>* _left;
	BSTNode<K, V>* _right;
	BSTNode(const K& key, const V& value) 
		:_key(key)
		, _value(value)
		, _left(nullptr)
		, _right(nullptr)
	{}
};
template<class K, class V>
class BSTree
{
	typedef BSTNode<K, V> Node;
public:
	BSTree() = default;
	BSTree(const BSTree<K, V>& t)
	{
		_root = Copy(t._root);
	}
	BSTree<K, V>& operator=(BSTree<K, V> t)
	{
		swap(_root, t._root);
		return *this;
	}
	~BSTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
	bool Insert(const K& key, const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node(key, value);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key, value);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
					delete cur;
					return true;
				}
				else
				{
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}
					cur->_key = rightMin->_key;
					if (rightMinP->_left == rightMin)
						rightMinP->_left = rightMin->_right;
					else
						rightMinP->_right = rightMin->_right;
					delete rightMin;
					return true;
				}
			}
		}
		return false;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << ":" << root->_value << endl;
		_InOrder(root->_right);
	}
	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newRoot = new Node(root->_key, root->_value);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return newRoot;
	}
private:
	Node* _root = nullptr;
};
void test1()
{
	BSTree<string, string> dict;
	dict.Insert("left", "左边");
	dict.Insert("right", "右边");
	dict.Insert("insert", "插入");
	dict.Insert("string", "字符串");

	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << "->" << ret->_value << endl;
		}
		else
		{
			cout << "无此单词，请重新输入" << endl;
		}
	}
}

void test2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

	BSTree<string, int> t;
	for (auto str : arr)
	{
		auto pNode = t.Find(str);
		if (pNode == nullptr)
		{
			t.Insert(str, 1);
		}
		else
		{
			pNode->_value++;
		}
	}

	t.InOrder();
}
int main()
{

	test2();
	return 0;
}
